// https://leetcode.cn/problems/advantage-shuffle/
// Created by ade on 2022/10/8.
// 给定两个大小相等的数组 nums1 和 nums2，nums1 相对于 nums 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。
//
// 返回 nums1 的任意排列，使其相对于 nums2 的优势最大化。
// 输入：nums1 = [2,7,11,15], nums2 = [1,10,4,11]
// 输出：[2,11,7,15]

class Solution {
public:
    vector<int> advantageCount(vector<int> &nums1, vector<int> &nums2) {
        int n = nums1.size();
        vector<int> idx1(n);
        vector<int> idx2(n);
        iota(idx1.begin(), idx1.end(), 0);
        iota(idx2.begin(), idx2.end(), 0);

        sort(idx1.begin(), idx1.end(), [&](int i, int j) { return nums1[i] < nums1[j]; });
        sort(idx2.begin(), idx2.end(), [&](int i, int j) { return nums2[i] < nums2[j]; });
        int left = 0, right = n - 1;
        vector<int> ans(n);
        for (int i = 0; i < n; i++) {
            if (nums1[idx1[i]] > nums2[idx2[left]]) {
                ans[idx2[left]] = nums1[idx1[i]];
                left++;
            }else{
                ans[idx2[right]] = nums1[idx1[i]];
                right--;
            }
        }
        return ans;


    }
};

int main() {
    Solution so;

}